{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find the Longest Semi-Repetitive Substring"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: longestSemiRepetitiveSubstring"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找到最长的半重复子字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始的字符串&nbsp;<code>s</code>&nbsp;，这个字符串只包含&nbsp;<code>0</code>&nbsp;到&nbsp;<code>9</code>&nbsp;的数字字符。</p>\n",
    "\n",
    "<p>如果一个字符串&nbsp;<code>t</code>&nbsp;中至多有一对相邻字符是相等的，那么称这个字符串 <code>t</code> 是 <strong>半重复的</strong>&nbsp;。例如，<code>0010</code> 、<code>002020</code> 、<code>0123</code> 、<code>2002</code> 和 <code>54944</code> 是半重复字符串，而 <code>00101022</code> 和 <code>1101234883</code> 不是。</p>\n",
    "\n",
    "<p>请你返回 <code>s</code>&nbsp;中最长 <strong>半重复</strong>&nbsp;子字符串的长度。</p>\n",
    "\n",
    "<p>一个 <strong>子字符串</strong>&nbsp;是一个字符串中一段连续 <strong>非空</strong>&nbsp;的字符。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"52233\"\n",
    "<b>输出：</b>4\n",
    "<b>解释：</b>最长半重复子字符串是 \"5223\" ，子字符串从 i = 0 开始，在 j = 3 处结束。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"5494\"\n",
    "<b>输出：</b>4\n",
    "<b>解释：</b>s 就是一个半重复字符串，所以答案为 4 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"1111111\"\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>最长半重复子字符串是 \"11\" ，子字符串从 i = 0 开始，在 j = 1 处结束。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 50</code></li>\n",
    "\t<li><code>'0' &lt;= s[i] &lt;= '9'</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-the-longest-semi-repetitive-substring](https://leetcode.cn/problems/find-the-longest-semi-repetitive-substring/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-the-longest-semi-repetitive-substring](https://leetcode.cn/problems/find-the-longest-semi-repetitive-substring/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"52233\"', '\"5494\"', '\"1111111\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        list1,ans=[0,0],0\n",
    "        for i in range(1,len(s)):\n",
    "            if(s[i]==s[i-1]):\n",
    "                ans = max(ans,i-list1[0])\n",
    "                list1=[list1[1],i]\n",
    "        ans = max(ans,len(s)-list1[0])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        if len(s)<2:\n",
    "            return 1\n",
    "        left,right=0,1\n",
    "        res=0\n",
    "        flag=0\n",
    "        last=0\n",
    "        if s[left]==s[right]:\n",
    "            flag=1\n",
    "            res=right-left+1\n",
    "            last=right\n",
    "        while right<len(s)-1:\n",
    "            if s[right]==s[right+1] :\n",
    "                if flag==1:\n",
    "                    res=max(res,right-left+1)\n",
    "                    left=last\n",
    "                    \n",
    "                    last=right+1\n",
    "                elif flag==0:\n",
    "                    flag=1\n",
    "                    last=right+1\n",
    "            right+=1\n",
    "        #if s[right-1]==s[right]:\n",
    "        #    right-=1\n",
    "        res=max(res,right-left+1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        count=0\n",
    "        index1=0\n",
    "        index2=1\n",
    "        result=1\n",
    "        index3=-1\n",
    "        while index2<len(s):\n",
    "            if s[index2]!=s[index2-1]:\n",
    "                result=max(result,index2-index1+1)\n",
    "                index2+=1\n",
    "            else:\n",
    "                if count==0:\n",
    "                    index3=index2\n",
    "                    result=max(result,index2-index1+1)\n",
    "                    count+=1\n",
    "                else:\n",
    "                    index1=index3\n",
    "                    index3=index2\n",
    "                    result=max(result,index2-index1+1)\n",
    "                index2+=1\n",
    "\n",
    "        return result\n",
    "\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        if len(s)==1:\n",
    "            return 1\n",
    "        L=[0]\n",
    "        for i in range(1,len(s)):\n",
    "            if s[i]==s[i-1]:\n",
    "                L.append(i)\n",
    "        L.append(len(s))\n",
    "        if len(L)==2:\n",
    "            return len(s)\n",
    "        return max([j-i for i,j in zip(L[:-2],L[2:])])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        # \"1111111\"\n",
    "        # \"0001\"\n",
    "        res = 0\n",
    "        start = 0\n",
    "        fist_mark = 0\n",
    "        pre_num = \"x\"\n",
    "        cnt = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == pre_num:\n",
    "                cnt += 1\n",
    "                if cnt == 1:\n",
    "                    fist_mark = i\n",
    "                if cnt > 1:\n",
    "                    res = max(res, i - start)\n",
    "                    cnt = 1\n",
    "                    start = fist_mark\n",
    "                    fist_mark = i\n",
    "            pre_num = s[i]\n",
    "        return max(res, len(s) - start)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        \n",
    "        res = 1\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                cnt = [0]* 10\n",
    "                for d in range(10):\n",
    "                    dd = str(d) * 2\n",
    "                    ddd = str(d) * 3\n",
    "                    substr = s[i: j + 1]\n",
    "                    cnt[d] += substr.count(dd) + substr.count(ddd)\n",
    "                if sum(cnt) > 1:\n",
    "                    break\n",
    "                res = max(res, j - i + 1)\n",
    "        \n",
    "        return res\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        left = 0\n",
    "        repeat = 0\n",
    "        ans =1\n",
    "        for r in range(1,len(s)):\n",
    "            if s[r] == s[r-1]:\n",
    "                repeat+=1\n",
    "            if repeat>1:\n",
    "                left += 1\n",
    "                while s[left] != s[left - 1]:\n",
    "                    left += 1\n",
    "                repeat = 1\n",
    "            ans =max(ans,r-left+1)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        left = 0\n",
    "        ans = 0\n",
    "        q = -1\n",
    "        n = len(s)\n",
    "        for i in range(1,n):\n",
    "            if s[i] == s[i-1]:\n",
    "                if q == -1:\n",
    "                    q = i\n",
    "                else:\n",
    "                    ans = max(ans, i-left)\n",
    "                    left, q = q, i\n",
    "        ans = max(ans,n-left)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        ans, left, same = 1, 0, 0\n",
    "        for right in range(1, len(s)):\n",
    "            same += s[right] == s[right - 1]\n",
    "            if same > 1:\n",
    "                left += 1\n",
    "                while s[left] != s[left - 1]:\n",
    "                    left += 1\n",
    "                same = 1\n",
    "            ans = max(ans, right - left + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        result, a, b, n = 0, -1, -1, len(s)\n",
    "        for i in range(n-1):\n",
    "            if s[i] == s[i+1]:\n",
    "                result, a, b = max(result, i - a), b, i\n",
    "        return max(result, n - a - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        if n<=2:\n",
    "            return n\n",
    "        ans=0\n",
    "        i=j=0\n",
    "        for k in range(1,n):\n",
    "            if s[k]==s[k-1]:\n",
    "                i=j\n",
    "                j=k\n",
    "            if k-i+1>ans:\n",
    "                ans=k-i+1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ans = min(1, n)\n",
    "        for i in range(n):\n",
    "            last = s[i]\n",
    "            k = -1\n",
    "            for j in range(i + 1, n):\n",
    "                if s[j] == last:\n",
    "                    k += 1\n",
    "                    if k:\n",
    "                        ans = max(ans, j - i)\n",
    "                        break\n",
    "                last = s[j]\n",
    "            if k <= 0:\n",
    "                ans = max(ans, n - i)\n",
    "                break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        # 半重复最长子串： 相邻字符串最多一对相同\n",
    "        ans = 1\n",
    "        left = same = 0\n",
    "        for right in range(1, len(s)):\n",
    "            same += s[right] == s[right - 1] # 计数相同字符对数\n",
    "            if same > 1: # 缩窗\n",
    "                left += 1\n",
    "                while s[left] != s[left - 1]: # 确定唯一相同字符对下标：\n",
    "                    left += 1\n",
    "                same = 1\n",
    "            ans = max(ans, right - left + 1)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        paired = 0\n",
    "        L, R = 0, 1\n",
    "        ans = 0\n",
    "        while R < len(s):\n",
    "            if s[R] == s[R-1]:\n",
    "                paired += 1\n",
    "            while paired > 1:\n",
    "                L += 1\n",
    "                if s[L] == s[L-1]:\n",
    "                    paired -= 1\n",
    "            R += 1\n",
    "            ans = max(ans, R-L)\n",
    "                \n",
    "        return ans if paired else len(s)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        \n",
    "        window = Counter()\n",
    "        \n",
    "        # \n",
    "        cnt = 0\n",
    "        res = 1\n",
    "        left, right = 0, 1\n",
    "        while right < n:\n",
    "\n",
    "        # for right in range(1, n):\n",
    "            # 判断是否碰到重复子字符串\n",
    "            if s[right] == s[right - 1]:\n",
    "                cnt += 1\n",
    "            right += 1\n",
    "            # 确保区间内没有 重复子字符串 \n",
    "            while cnt >= 2 and left < right:\n",
    "                left += 1\n",
    "                # 缩减左边界\n",
    "                if s[left] == s[left - 1]:\n",
    "                    cnt -= 1\n",
    "\n",
    "            # 此时left停在边界的右侧 \n",
    "            res = max(res, right - left)\n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ans = min(1, n)\n",
    "        for i in range(n):\n",
    "            last = s[i]\n",
    "            k = -1\n",
    "            for j in range(i + 1, n):\n",
    "                if s[j] == last:\n",
    "                    k += 1\n",
    "                    if k:\n",
    "                        ans = max(ans, j - i)\n",
    "                        break\n",
    "                last = s[j]\n",
    "            if k <= 0:\n",
    "                ans = max(ans, n - i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        left, right = 0, 0\n",
    "        repcnt = 0\n",
    "        result = 0\n",
    "        while(right < n):\n",
    "            if(right == 0 or s[right] != s[right-1]):\n",
    "                result = max(result, right-left+1)\n",
    "                right += 1\n",
    "            else:\n",
    "                repcnt += 1\n",
    "                while(repcnt > 1 and left <= right):\n",
    "                    if(s[left] == s[left+1]):\n",
    "                        repcnt -= 1\n",
    "                    left += 1\n",
    "                result = max(result, right-left+1)\n",
    "                right += 1\n",
    "                \n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        l = 0\n",
    "        cnt = 0\n",
    "        n = len(s)\n",
    "        dp = [[0,0] for _ in range(n)]\n",
    "        dp[0][0] = 1\n",
    "        m = 1\n",
    "        for i in range(n):\n",
    "            if i == 0:\n",
    "                continue\n",
    "            if i > 0 and s[i] == s[i - 1]:\n",
    "                dp[i][1] = max(dp[i - 1][0] + 1,dp[i][1])\n",
    "                dp[i][0] = 1\n",
    "            else:\n",
    "                dp[i][0] = dp[i - 1][0] + 1\n",
    "                dp[i][1] = dp[i - 1][1] + 1\n",
    "            m = max(m,dp[i][0],dp[i][1])\n",
    "        return m\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        left = 0\n",
    "        same = 0\n",
    "        ans = 1\n",
    "        for right in range(1, n):\n",
    "            if s[right]==s[right-1]:\n",
    "                same += 1\n",
    "            while same>=2:\n",
    "                if s[left]==s[left+1]:\n",
    "                    same -= 1\n",
    "                left += 1\n",
    "            ans = max(ans, right-left+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        l, r = 0, 0\n",
    "        res = 0\n",
    "        v = True\n",
    "        n = len(s)\n",
    "        for i in range(1, n):\n",
    "            if s[i] == s[i - 1] and v:\n",
    "                v = False\n",
    "                r = i\n",
    "                continue\n",
    "            if s[i] == s[i - 1] and not v:\n",
    "                res = max(res, i - l)\n",
    "                l = r\n",
    "                r = i\n",
    "\n",
    "        res = max(res, n - l)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        ans = 1\n",
    "        n = len(s)\n",
    "        left = 0\n",
    "        sam_cnt = 0\n",
    "        for right in range(1, n):\n",
    "            if s[right] == s[right - 1]: sam_cnt += 1\n",
    "            if sam_cnt > 1:\n",
    "                left += 1\n",
    "                while s[left] != s[left-1]:\n",
    "                    left += 1\n",
    "                sam_cnt = 1\n",
    "            ans = max(ans, right - left + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        ans = 1\n",
    "        left, cur = 0, 0\n",
    "        for right in range(1, len(s)):\n",
    "            cur += s[right] == s[right-1]\n",
    "            if cur > 1:\n",
    "                left += 1\n",
    "                while(s[left] != s[left-1]):\n",
    "                    left += 1\n",
    "                cur = 1\n",
    "            ans = max(ans, right-left+1)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        if len(s)<=2:\n",
    "            return len(s)\n",
    "        l,ans,pre = 0,1,0\n",
    "        for i in range(1,len(s)):\n",
    "            if s[i]==s[i-1]:\n",
    "                pre,l=l,i\n",
    "            ans = max(ans,i-pre+1) \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        pos = []\n",
    "        for i in range(1, len(s)):\n",
    "            if s[i] == s[i - 1]:\n",
    "                pos.append(i)\n",
    "\n",
    "        n = len(pos)\n",
    "        if n <= 1:\n",
    "            return len(s)\n",
    "        res = pos[1]\n",
    "\n",
    "        for i in range(2, len(pos)):\n",
    "            res = max(res, pos[i] - pos[i - 2])\n",
    "        res = max(res, len(s) - pos[-2])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        res = 0\n",
    "        j = 0\n",
    "        i = 0\n",
    "        cnt = 0\n",
    "        while i < len(s):\n",
    "            if i and s[i] == s[i - 1]:\n",
    "                cnt += 1\n",
    "            while cnt > 1 and j < i:\n",
    "                if s[j] == s[j + 1]:\n",
    "                    cnt -= 1\n",
    "                j += 1\n",
    "            res = max(res, i - j + 1)\n",
    "            i += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        q, m = deque((0, 0)), 0\n",
    "        for i in range(1, len(s)):\n",
    "            if s[i] != s[i - 1]:\n",
    "                continue\n",
    "            m = max(m, i - q.popleft())\n",
    "            q.append(i)\n",
    "        return max(m, len(s) - q.popleft())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        result, a, b, n = 0, -1, -1, len(s)\n",
    "        for i in range(n-1):\n",
    "            if s[i] == s[i+1]:\n",
    "                result = max(result, i - a)\n",
    "                a, b = b, i\n",
    "        return max(result, n - a - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ans= 0\n",
    "        l = 0\n",
    "        cnt = 0\n",
    "        for r in range(n):\n",
    "            if r and s[r] == s[r-1]:\n",
    "                cnt +=1\n",
    "            while cnt > 1 and l < r:\n",
    "                l+=1\n",
    "                if s[l] == s[l-1]:\n",
    "                    cnt -=1\n",
    "            ans = max(ans, r - l +1)\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        left, right = 0, 0\n",
    "        repcnt = 0\n",
    "        result = 0\n",
    "        while(right < n):\n",
    "            if(right == 0 or s[right] != s[right-1]):\n",
    "                result = max(result, right-left+1)\n",
    "                right += 1\n",
    "            else:\n",
    "                repcnt += 1\n",
    "                while(repcnt > 1 and left <= right):\n",
    "                    if(s[left] == s[left+1]):\n",
    "                        repcnt -= 1\n",
    "                    left += 1\n",
    "                result = max(result, right-left+1)\n",
    "                right += 1\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        ans = 1\n",
    "        left = mid = 0\n",
    "        for i in range(1, len(s)):\n",
    "            if s[i] == s[i - 1]:\n",
    "                if i - left > ans:\n",
    "                    ans = i - left\n",
    "                left, mid = mid, i\n",
    "\n",
    "        return max(ans, len(s) - left)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        prev=''\n",
    "        left=right=ans=0\n",
    "        rep=0\n",
    "        while right<n:\n",
    "            if s[right]==prev:\n",
    "                rep += 1\n",
    "            prev=s[right]\n",
    "            while rep>=2:\n",
    "                if s[left]==s[left+1]:\n",
    "                    rep -= 1\n",
    "                left += 1\n",
    "            ans=max(ans,right-left+1)\n",
    "            right += 1\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        ans , left, cnt = 1, 0, 0\n",
    "        n = len(s)\n",
    "        for i in range(1,n):\n",
    "            cnt += (s[i] == s[i-1])\n",
    "            while cnt > 1:\n",
    "                left += 1\n",
    "                if s[left] == s[left-1]:\n",
    "                    cnt -=1\n",
    "            ans = max(ans, i - left + 1)        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            sign=0\n",
    "            for j in range(i,n):\n",
    "                if j>i and s[j]==s[j-1] and sign==0:\n",
    "                    sign=1\n",
    "                elif j>i and s[j]==s[j-1] and sign==1:\n",
    "                    ans=max(ans,j-i)\n",
    "                    break\n",
    "                ans=max(ans,j-i+1)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        l = len(s)\n",
    "        if l < 2:\n",
    "            return l \n",
    "        ans = 0\n",
    "        i = 0\n",
    "        j = 1\n",
    "        while j<l and s[j]!= s[j-1]:\n",
    "            j+=1\n",
    "        if j>=l:\n",
    "            return l \n",
    "        ans = j-i+1\n",
    "        repeat_char_idx = j-1\n",
    "        j += 1\n",
    "        while j<l:\n",
    "            while j<l and s[j]!= s[j-1]:\n",
    "                ans = max(ans, j-i+1)\n",
    "                j+=1\n",
    "            if j==l:\n",
    "                return ans\n",
    "            ans = max(ans, j - repeat_char_idx)\n",
    "            i = repeat_char_idx+1\n",
    "            repeat_char_idx = j-1\n",
    "            j+=1\n",
    "        return ans\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        if n<=2:\n",
    "            return n\n",
    "        ans=0\n",
    "        i=j=0\n",
    "        for k in range(1,n):\n",
    "            if s[k]==s[k-1]:\n",
    "                i=j\n",
    "                j=k\n",
    "            if k-i+1>ans:\n",
    "                ans=k-i+1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        j = 0\n",
    "        last = 0\n",
    "        cnt = 0\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if i > 0 and s[i] == s[i - 1]:\n",
    "                cnt += 1\n",
    "                if cnt > 1:\n",
    "                    j = last\n",
    "                last = i\n",
    "            ans = max(ans, i - j + 1)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        ans, left, same = 1, 0, 0\n",
    "        for right in range(1, len(s)):\n",
    "            same += s[right] == s[right - 1]\n",
    "            if same > 1:\n",
    "                left += 1\n",
    "                while s[left] != s[left - 1]:\n",
    "                    left += 1\n",
    "                same = 1\n",
    "            ans = max(ans, right - left + 1)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        ans, left, same = 1, 0, 0\n",
    "        for right in range(1, len(s)):\n",
    "            same += s[right] == s[right - 1]\n",
    "            if same > 1:\n",
    "                left += 1\n",
    "                while s[left] != s[left - 1]:\n",
    "                    left += 1\n",
    "                same = 1\n",
    "            ans = max(ans, right - left + 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\r\n",
    "        left = 0\r\n",
    "        ans = 0\r\n",
    "        q = -1\r\n",
    "        n = len(s)\r\n",
    "        for i in range(1,n):\r\n",
    "            if s[i] == s[i-1]:\r\n",
    "                if q == -1:\r\n",
    "                    q = i\r\n",
    "                else:\r\n",
    "                    ans = max(ans, i-left)\r\n",
    "                    left, q = q, i\r\n",
    "        ans = max(ans,n-left)\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        i = j = 0\n",
    "        cnt = 0\n",
    "        while j < len(s):\n",
    "            if j - 1 >= 0 and s[j] == s[j - 1]:\n",
    "                cnt += 1\n",
    "\n",
    "            while i <= j and cnt > 1:\n",
    "                if s[i] == s[i + 1]:\n",
    "                    cnt -= 1\n",
    "\n",
    "                i += 1\n",
    "\n",
    " \n",
    "            ans = max(ans, j - i + 1)\n",
    "\n",
    "            j += 1\n",
    "\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        if len(s) == 1:\n",
    "            return 1\n",
    "        left, right = 0, 0\n",
    "        ans = 1\n",
    "        cur = 0\n",
    "        idx = 0\n",
    "        while(right < len(s)-1):\n",
    "            while(cur <= 1 and right < len(s)-1):\n",
    "                if s[right] == s[right+1]:\n",
    "                    cur += 1\n",
    "                    # if cur == 1:\n",
    "                    #     idx = right+1\n",
    "                right += 1\n",
    "            if cur == 2:\n",
    "                ans = max(ans, right-left)\n",
    "            else:\n",
    "                ans = max(ans, right-left+1)\n",
    "            left += 1\n",
    "            while(left < len(s) and s[left] != s[left-1]):\n",
    "                left += 1\n",
    "            cur = 1\n",
    "            # idx = right\n",
    "        return max(ans, right-left)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        ans = 1\n",
    "        left = same = 0\n",
    "        for right in range(1, len(s)):\n",
    "            same += s[right] == s[right - 1]\n",
    "            if same > 1:\n",
    "                left += 1\n",
    "                while s[left] != s[left - 1]:\n",
    "                    left += 1\n",
    "                same = 1\n",
    "            ans = max(ans, right - left + 1)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        left, right = 0, 0\n",
    "        repcnt = 0\n",
    "        result = 0\n",
    "        while(right < n):\n",
    "            if(right == 0 or s[right] != s[right-1]):\n",
    "                result = max(result, right-left+1)\n",
    "                right += 1\n",
    "            else:\n",
    "                repcnt += 1\n",
    "                while(repcnt > 1 and left <= right):\n",
    "                    if(s[left] == s[left+1]):\n",
    "                        repcnt -= 1\n",
    "                    left += 1\n",
    "                result = max(result, right-left+1)\n",
    "                right += 1\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        # 双指针\n",
    "        maxDistance = curDistance = 1  # 设最长距离, 当前距离, 初始值都为1\n",
    "        lastPair_y = -1  # 记录前一对重复字符的结尾下标\n",
    "        for j in range(1, len(s)):\n",
    "            if s[j] != s[j-1]:  # 如当前字符与前一个字符不相等, 当前距离加1\n",
    "                curDistance += 1\n",
    "            else:\n",
    "                # 当前字符与前一字符相等的情况,分别讨论\n",
    "                # 1.如果lastPair_y没有改动过,说明前面没有出现过重复字符对, 当前距离加1\n",
    "                if lastPair_y == -1:\n",
    "                    curDistance += 1\n",
    "                else:\n",
    "                    # 2.前面已经出现过重复字符对, 更新记录最长距离\n",
    "                    # 新的距离,从前一对重复字符结尾处开始重新计算\n",
    "                    maxDistance = max(maxDistance, curDistance)\n",
    "                    curDistance = j - lastPair_y + 1\n",
    "                lastPair_y = j  # 更新前一重复字符对的结尾下标\n",
    "        return max(maxDistance, curDistance)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        def judge(t):\n",
    "            k = len(t)\n",
    "            cnt = 0\n",
    "            for i in range(k-1):\n",
    "                if t[i] == t[i+1]:\n",
    "                    cnt += 1\n",
    "            return cnt <= 1\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        if len(s) == 1:\n",
    "            return 1\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                if judge(s[i:j+1]):\n",
    "                    ans = max(ans,j-i+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        res = 0\n",
    "        j = 0\n",
    "        i = 0\n",
    "        cnt = 0\n",
    "        while i < len(s):\n",
    "            if i and s[i] == s[i - 1]:\n",
    "                cnt += 1\n",
    "            while cnt > 1 and j < i:\n",
    "                if s[j] == s[j + 1]:\n",
    "                    cnt -= 1\n",
    "                j += 1\n",
    "            res = max(res, i - j + 1)\n",
    "            i += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        left,cont,ans = 0,0,0 \n",
    "        if(len(s) == 1):\n",
    "            return 1\n",
    "        for right in range(1,len(s)):\n",
    "            cont += s[right]==s[right-1]\n",
    "            if cont >1:\n",
    "                left+=1\n",
    "                while(s[left]!=s[left-1]):\n",
    "                    left+=1\n",
    "                cont=1\n",
    "            ans = max(ans,right-left+1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        i, j = 0, 0\n",
    "        n = len(s)\n",
    "        cnt = 0\n",
    "        ans = 0\n",
    "        while j < n:\n",
    "            if j > 0 and s[j] == s[j - 1]:\n",
    "                cnt += 1\n",
    "            while cnt > 1:\n",
    "                if s[i] == s[i + 1]:\n",
    "                    cnt -= 1\n",
    "                i += 1\n",
    "            ans = max(ans, j - i + 1)\n",
    "            j += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        ans, left, same = 1, 0, 0\n",
    "        for right in range(1, len(s)):\n",
    "            same += s[right] == s[right - 1]\n",
    "            if same > 1:\n",
    "                left += 1\n",
    "                while s[left] != s[left - 1]:\n",
    "                    left += 1\n",
    "                same -= 1\n",
    "            ans = max(ans, right - left + 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        ans = 1\n",
    "        left = 0\n",
    "        same = 0\n",
    "        for right in range(1, len(s)):\n",
    "            same += s[right] == s[right - 1]\n",
    "            if same == 2:\n",
    "                left += 1\n",
    "                while s[left] != s[left-1]:\n",
    "                    left += 1\n",
    "                same = 1\n",
    "            ans = max(ans, right - left + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        #解题思路：\n",
    "        #需要记录下每对相邻字符 的前一个，再依据这些字符的位置来进行判断\n",
    "        #例如，52233,[-1,i,j,n]\n",
    "        \n",
    "        alist = []\n",
    "        n = len(s)\n",
    "        for i in range(1,n):\n",
    "            if s[i] == s[i - 1]:\n",
    "                alist.append(i)\n",
    "        # print(n,alist)\n",
    "        if len(alist) <= 1:\n",
    "            return n\n",
    "        res = alist[1]\n",
    "        for i in range(2,len(alist)):\n",
    "            res = max(res,alist[i] - alist[i - 2])\n",
    "        res = max(n - alist[-2],res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        sub_len = []\n",
    "        temp_len = 1\n",
    "        for i in range(len(s) - 1):\n",
    "            if s[i + 1] == s[i]:\n",
    "                sub_len.append(temp_len)\n",
    "                temp_len = 1\n",
    "            else:\n",
    "                temp_len += 1\n",
    "            if i == len(s) - 2:\n",
    "                sub_len.append(temp_len)\n",
    "        if len(sub_len)==1:\n",
    "            return sub_len[0]\n",
    "        else:\n",
    "            m = 1\n",
    "            for i in range(len(sub_len) - 1):\n",
    "                if sub_len[i] + sub_len[i + 1] > m:\n",
    "                    m = sub_len[i] + sub_len[i + 1]\n",
    "            return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        # 滑动窗口\n",
    "        i = j = 0\n",
    "        pair = 0\n",
    "        ans = 0\n",
    "        while j < len(s):\n",
    "            if j > 0 and s[j] == s[j-1]:\n",
    "                pair += 1\n",
    "            while pair > 1:\n",
    "                i += 1\n",
    "                if s[i]==s[i-1]:\n",
    "                    pair -= 1\n",
    "            ans = max(ans, j-i+1)\n",
    "            j += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ans = 1\n",
    "        left = 0\n",
    "        dup_cnt = 0\n",
    "        for right in range(1, n):\n",
    "            if s[right] == s[right - 1]:\n",
    "                dup_cnt += 1\n",
    "            if dup_cnt > 1:\n",
    "                left += 1\n",
    "                while s[left] != s[left - 1]:\n",
    "                    left += 1\n",
    "                dup_cnt -= 1\n",
    "            ans = max(ans, right - left + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        ans, left, same = 1, 0, 0\n",
    "        for right in range(1, len(s)):\n",
    "            same += s[right] == s[right - 1]\n",
    "            if same > 1:\n",
    "                left += 1\n",
    "                while s[left] != s[left - 1]:\n",
    "                    left += 1\n",
    "                same = 1\n",
    "            ans = max(ans, right - left + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        ans, left, same = 1,0,0\n",
    "        for right in range(1,len(s)):\n",
    "            same += s[right] == s[right-1]\n",
    "            if same > 1:\n",
    "                left += 1\n",
    "                while s[left] != s[left-1]:\n",
    "                    left += 1\n",
    "                same = 1\n",
    "            ans = max(ans,right-left+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        if n<=2:\n",
    "            return n\n",
    "        cnt=0\n",
    "        ans=0\n",
    "        i=j=0\n",
    "        for k in range(1,n):\n",
    "            if s[k]==s[k-1]:\n",
    "                i=j\n",
    "                j=k\n",
    "            if k-i+1>ans:\n",
    "                ans=k-i+1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        ans = 1\n",
    "        n = len(s)\n",
    "        left, same = 0, 0\n",
    "        for right in range(1, n):\n",
    "            same += (s[right] == s[right - 1])\n",
    "            if same > 1:\n",
    "                left += 1\n",
    "                while s[left] != s[left - 1]:\n",
    "                    left += 1\n",
    "                same = 1\n",
    "            ans = max(ans, right - left + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        res = 1\n",
    "        count = 0\n",
    "        i1 = 0\n",
    "        for i2 in range(1, n):\n",
    "            if s[i2] == s[i2-1]:\n",
    "                count += 1\n",
    "            if count == 2:\n",
    "                while s[i1] != s[i1+1]:\n",
    "                    i1 += 1\n",
    "                i1 += 1\n",
    "                count -= 1\n",
    "            res = max(res, i2 - i1 + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        ans  = 1\n",
    "        l = 0\n",
    "        n = len(s)\n",
    "        cnt = 0\n",
    "        for r in range(n):\n",
    "            if r and s[r] == s[r-1]:\n",
    "                cnt +=1\n",
    "            while cnt > 1 and l<r:\n",
    "                l+=1\n",
    "                if s[l] == s[l-1]:\n",
    "                    cnt -=1\n",
    "            if l <r :        \n",
    "                ans = max(ans, r - l +1)\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        ans, left, same = 1, 0, 0\n",
    "        for right in range(1, len(s)):\n",
    "            same += s[right] == s[right - 1]\n",
    "            if same > 1:\n",
    "                left += 1\n",
    "                while s[left] != s[left - 1]:\n",
    "                    left += 1\n",
    "                same = 1\n",
    "            ans = max(ans, right - left + 1)\n",
    "        return ans\n",
    "\n",
    "# 作者：灵茶山艾府\n",
    "# 链接：https://leetcode.cn/problems/find-the-longest-semi-repetitive-substring/solutions/2304713/shuang-zhi-zhen-hua-chuang-pythonjavacgo-nurf/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ans, left, same = 1, 0, 0\n",
    "        for right in range(1, n):\n",
    "            same += s[right]==s[right-1]\n",
    "            if same==2:\n",
    "                left += 1\n",
    "                while s[left] != s[left-1]: # 没有碰到两个相邻相同字符，跳出循环时left落在后一个相同字符处\n",
    "                    left += 1\n",
    "                same = 1\n",
    "            ans = max(ans, right-left+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        \n",
    "        window = Counter()\n",
    "        \n",
    "        # \n",
    "        cnt = 0\n",
    "        res = 1\n",
    "        left = 0\n",
    "        for right in range(1, n):\n",
    "            # 判断是否碰到重复子字符串\n",
    "            if s[right] == s[right - 1]:\n",
    "                cnt += 1\n",
    "            # 确保区间内没有 重复子字符串 \n",
    "            while cnt >= 2 and left < right:\n",
    "                left += 1\n",
    "                # 缩减左边界\n",
    "                if s[left] == s[left - 1]:\n",
    "                    cnt -= 1\n",
    "\n",
    "            # 此时left停在边界的右侧 \n",
    "            res = max(res, right - left + 1)\n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "\n",
    "        left = 1\n",
    "        right = len(s)\n",
    "\n",
    "        def check(tar):\n",
    "\n",
    "            ans = 0\n",
    "\n",
    "            for i in range(1, tar):\n",
    "                if s[i] == s[i - 1]:\n",
    "                    ans += 1\n",
    "\n",
    "            if ans <= 1:\n",
    "                return True\n",
    "\n",
    "            left = 0\n",
    "            right = tar - 1\n",
    "\n",
    "            left += 1\n",
    "            right += 1\n",
    "\n",
    "            while right < len(s):\n",
    "                if s[right] == s[right - 1]:\n",
    "                    ans += 1\n",
    "                \n",
    "                if s[left] == s[left - 1]:\n",
    "                    ans -= 1\n",
    "\n",
    "                if ans <= 1:\n",
    "                    return True\n",
    "\n",
    "                left += 1\n",
    "                right += 1\n",
    "\n",
    "            return False\n",
    "\n",
    "        while left < right:\n",
    "            mid = left + (right - left + 1) // 2\n",
    "\n",
    "            if check(mid):\n",
    "                left = mid\n",
    "            else:\n",
    "                right= mid - 1\n",
    "        \n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\r\n",
    "        n = len(s)\r\n",
    "        if n < 3:\r\n",
    "            return n\r\n",
    "        lf, rt = 0, 1\r\n",
    "        res = 0\r\n",
    "        same = 0\r\n",
    "        while rt < len(s):\r\n",
    "            same += s[rt] == s[rt-1]\r\n",
    "            if same > 1:\r\n",
    "                lf += 1\r\n",
    "                while s[lf] != s[lf-1]:\r\n",
    "                    lf += 1\r\n",
    "                same = 1\r\n",
    "            res = max(res, rt - lf + 1)\r\n",
    "            rt += 1\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        if len(s) == 1:\n",
    "            return 1\n",
    "        left, right = 0, 0\n",
    "        ans,cur = 1, 0\n",
    "        while(right < len(s)-1):\n",
    "            while(cur <= 1 and right < len(s)-1):\n",
    "                if s[right] == s[right+1]:\n",
    "                    cur += 1\n",
    "                right += 1\n",
    "            if cur == 2:\n",
    "                ans = max(ans, right-left)\n",
    "            else:\n",
    "                ans = max(ans, right-left+1)\n",
    "            left += 1\n",
    "            while(left < len(s) and s[left] != s[left-1]):\n",
    "                left += 1\n",
    "            cur = 1\n",
    "        return max(ans, right-left)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "\n",
    "        l = r = 0\n",
    "\n",
    "        n = len(s)\n",
    "\n",
    "        cnt = 0\n",
    "        ans = 0\n",
    "        while r<n:\n",
    "            if r >0 and s[r]==s[r-1]:\n",
    "                cnt +=1 \n",
    "\n",
    "            while l<r and cnt > 1:\n",
    "                l+=1\n",
    "                if s[l]==s[l-1]:\n",
    "                    cnt-=1\n",
    "            ans = max(ans,r-l+1)\n",
    "            # print(cnt)\n",
    "            r +=1\n",
    "\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        ans = 1\n",
    "        left = 0\n",
    "        cnt = 0\n",
    "        for right in range(1, len(s)):\n",
    "            if s[right - 1] == s[right]:\n",
    "                cnt += 1\n",
    "                if cnt > 1:\n",
    "                    left += 1\n",
    "                    while s[left] != s[left - 1]:\n",
    "                        left += 1\n",
    "                    cnt -= 1\n",
    "            ans = max(ans, right - left + 1)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        ans = 1\n",
    "        left = 0\n",
    "        same = 0\n",
    "        for right in range(1, len(s)):\n",
    "            same += s[right] == s[right - 1]\n",
    "            if same > 1:\n",
    "                left += 1\n",
    "                while s[left] != s[left-1]:\n",
    "                    left += 1\n",
    "                same = 1\n",
    "            ans = max(ans, right - left + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        l, r = 0, 0\n",
    "        cnt = 0\n",
    "        ans = 0\n",
    "        n = len(s)\n",
    "        while True:\n",
    "            while r < n and cnt + (s[r] == s[r-1]) < 2:\n",
    "                cnt += (s[r] == s[r-1] and r > 0)\n",
    "                r += 1\n",
    "            ans = max(ans, r - l)\n",
    "            if l == n-1: break\n",
    "            cnt -= s[l] == s[l+1]\n",
    "            l += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 同向双指针（滑动窗口）\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        ans, left, same = 1, 0, 0\n",
    "        for right in range(1, len(s)):\n",
    "            same += s[right] == s[right - 1]\n",
    "            if same > 1:\n",
    "                left += 1\n",
    "                while s[left] != s[left - 1]:\n",
    "                    left += 1\n",
    "\n",
    "                same = 1\n",
    "\n",
    "            ans = max(ans, right - left + 1)\n",
    "            \n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        if n == 1: return 1\n",
    "        l = 0\n",
    "        r = 1\n",
    "        maxn = 1\n",
    "        cur = 0\n",
    "        ans = 0\n",
    "        while r < n:\n",
    "            if s[r] == s[r-1]:\n",
    "                cur += 1\n",
    "            while cur > 1:\n",
    "                if s[l] == s[l + 1]:\n",
    "                    cur -= 1\n",
    "                l += 1\n",
    "            r += 1\n",
    "            ans = max(ans, r - l)\n",
    "        return ans\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        ans, left, same = 1, 0, 0\n",
    "        for right in range(1, len(s)):\n",
    "            same += s[right] == s[right - 1]\n",
    "            if same > 1:\n",
    "                left += 1\n",
    "                while s[left] != s[left - 1]:\n",
    "                    left += 1\n",
    "                same = 1\n",
    "            ans = max(ans, right - left + 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        ans = 1\n",
    "        a = 0\n",
    "        b = 0\n",
    "        for j in range(1, len(s)): \n",
    "            if s[j]==s[j-1]:\n",
    "                b+=1\n",
    "                while b>1:\n",
    "                    a+=1 \n",
    "                    if s[a]==s[a-1]:\n",
    "                        b-=1\n",
    "            ans = max(ans, j-a+1)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        if n == 1: return 1\n",
    "        l = cur = ans = 0\n",
    "        r = 1\n",
    "        while r < n:\n",
    "            if s[r] == s[r-1]:\n",
    "                cur += 1\n",
    "            while cur > 1:\n",
    "                if s[l] == s[l + 1]:\n",
    "                    cur -= 1\n",
    "                l += 1\n",
    "            r += 1\n",
    "            ans = max(ans, r - l)\n",
    "        return ans\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        left = 0\n",
    "        cnt = 0\n",
    "        ans = 1\n",
    "        for right in range(1, n):\n",
    "            if s[right] == s[right - 1]:\n",
    "                cnt += 1\n",
    "            while cnt > 1:\n",
    "                if s[left] == s[left + 1]:\n",
    "                    cnt -= 1\n",
    "                left += 1\n",
    "            ans = max(ans, right - left + 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        #最大滑动窗口\n",
    "        left,same,ans = 0,0,1\n",
    "        for i in range(1,len(s)):\n",
    "            same += s[i] == s[i-1]\n",
    "            if same > 1:\n",
    "                left+=1\n",
    "                while s[left] != s[left-1]:\n",
    "                    left+=1\n",
    "                same = 1\n",
    "            ans = max(ans,i-left + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSemiRepetitiveSubstring(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        l = [0]\n",
    "        for i in range(1,n):\n",
    "            if s[i] == s[i-1]:\n",
    "                l.append(i)\n",
    "        l.append(n)\n",
    "        n1 = len(l)\n",
    "        if n1 == 3 or n1 == 2:\n",
    "            return n\n",
    "        k =[]\n",
    "        for i in range(n1-2):\n",
    "            k.append(l[i+2]-l[i])\n",
    "        return max(k)\n",
    "            "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
